Tags: binary search, verifying recursion
Suppose we modify binary_search so that instead of using the floor operation to find the middle element of the array, we use the ceiling operation (recall that the ceiling of a real number \(x\) is the smallest integer that is \(\geq x\)). The full code is shown below for convenience:
import math
def new_binary_search(arr, start, stop, target):
if stop <= start:
return None
middle = math.ceil((start + stop) / 2)
if arr[middle] == target:
return middle
elif arr[middle] < target:
return new_binary_search(arr, middle + 1, stop, target)
else:
return new_binary_search(arr, start, middle, target)
Which of the following statements about the correctness of new_binary_search is true? You may assume that arr will be a list containing at least one number, and that the initial call to new_binary_search will be with start = 0 and stop
= len(arr) - 1.
new_binary_search may recurse infinitely
Tags: verifying recursion
Consider the code below which claims to compute the maximum of the input array. Adopt the convention that the maximum of an empty array is \(-\infty\).
import math
def maximum(arr, start=0, stop=None):
"""Find the maximum of arr[start:stop]."""
if stop is None:
stop = len(arr)
if stop - start == 0:
return -float('inf')
middle = math.floor((start + stop) / 2)
left = maximum(arr, start, middle)
right = maximum(arr, middle, stop)
if left > right:
return left
else:
return right
Will this code always return the correct answer (the maximum)? If yes, simply say so. If no, describe what might happen (recurse infinitely, return the wrong answer, raise an index error, etc.).
This code will recurse infinitely when called on an array with a single element.
Tags: recursion, verifying recursion
Consider the code below which claims to compute the most common element in the array, returning a pair: the element along with the number of times it appears.
import math
def most_common(arr, start, stop):
"""Attempts to compute the most common element in arr[start:stop]."""
if stop - start == 1:
return (arr[start], 1)
middle = math.floor((start + stop) / 2)
left_value, left_count = most_common(arr, start, middle)
right_value, right_count = most_common(arr, middle, stop)
if left_count > right_count:
return (left_value, left_count)
else:
return (right_value, right_count)
You may assume that the function is always called on a non-empty array, and with start = 0 and stop = len(arr). Will this code always return the correct answer (the most common element)?
No: it will run without error, but the element returned may not be the most common element in the array.
It is not true in general that the most common element in the array is the most common in the left or the right. As a simple example, take: [1,1,1,0,0,2,2,2,0,0]. 1 is the most common in the left half, and 2 is the most common in the right half, but 0 is the most common overall.
So even if we assume that most_common(arr, start, middle) finds the most common element in left half of the array, and most_common(arr, middle, stop) finds the most common element in the right of the array, it is not necessarily the case that the most common between them is the overall most common in the array.
You can also quickly see that the code cannot be correct because nowhere is a count greater than one ever returned.
Tags: binary search, recursion, verifying recursion
Suppose we modify binary_search so that instead of using the floor operation to find the middle element of the array, we use the ceiling operation (recall that the ceiling of a real number \(x\) is the smallest integer that is \(\geq x\)). The full code is shown below for convenience:
import math
def new_binary_search(arr, start, stop, target):
if stop <= start:
return None
middle = math.ceil((start + stop) / 2)
if arr[middle] == target:
return middle
elif arr[middle] < target:
return new_binary_search(arr, middle + 1, stop, target)
else:
return new_binary_search(arr, start, middle, target)
You may assume that arr will be a sorted list containing at least one number, and that the initial call to new_binary_search will be with start = 0 and stop = len(arr).
True or False: there are input arrays on which new_binary_search will recurse infinitely.
True.
True or False: there are input arrays on which new_binary_search will raise an IndexError because it attempts to access an element of the array which does not exist.
True.